package org.example.leetcode;

/**
 * @author: lynn
 * @Descript:
 * @date: 2021/8/5 8:16
 * @version: 1.0
 */
public class LC53 {
    public static void main(String[] args) {
        int[] nums={-2,1,-3,4,-1,2,1,-5,4};
        LC53 lc=new LC53();
        System.out.println(lc.maxSubArray(nums));
    }
    //fixme https://www.bilibili.com/video/BV1UT4y1w7ZG?from=search&seid=8172474563429301466
    //fixme 动态规划 https://leetcode-cn.com/problems/maximum-subarray/solution/dong-tai-gui-hua-fen-zhi-fa-python-dai-ma-java-dai/
    public int maxSubArray(int[] nums) {
        //动态转移方程
        // -2 1 -3 4 -1 2 1 -5 4
        // -2 1 -2 4  3 5 6  1 5
        int[] dp=new int[nums.length];// 表示以 nums[i] 结尾 的 连续 子数组的最大和。
        dp[0]=nums[0];
        for (int i = 1; i <=nums.length ; i++) {
            if (dp[i-1]<0){
                dp[i]=nums[i];
            }else {
                dp[i]=dp[i-1]+nums[i];
            }
        }

        int max=Integer.MIN_VALUE;
        for (int i = 0; i <dp.length-1 ; i++) {
            max=Math.max(dp[i],max);
        }
        return max;
    }
}
